package ee.homework.eighth;

/**
 *  Implementation of Warshall algorithm
 *  
 * @author Kaarel Hanson
 */
public class Warshall {

	public static void main(String[] args) {
		Warshall tc = new Warshall();
		tc.run();
	}

	public void run() {
		int[][] matrix = new int[][] { 
				{ 0, 1, 0, 0, 0 }, 
				{ 0, 0, 0, 1, 1 },
				{ 1, 0, 0, 0, 0 }, 
				{ 1, 0, 0, 0, 1 }, 
				{ 0, 0, 0, 0, 0 } 
		};
		
		System.out.println("Transitive closure");
		print(transitiveClosure(matrix));
	}
	
	public int[][] transitiveClosure(int[][] matrix) {
		int[][] result = new int[matrix.length][matrix[0].length];
		for (int i = 0; i < result.length; i++) {
			for (int j = 0; j < result[0].length; j++) {
				result[i][j] = matrix[i][j];
			}
		}

		for (int i = 0; i < result.length; i++) {
			for (int j = 0; j < result[0].length; j++) {
				if (result[j][i] == 1) {
					for (int k = 0; k < result.length; k++) {
						if (result[i][k] == 1) {
							result[j][k] = 1;
						}
					}
				}
			}
		}
		return result;
	}
	
	public void print(int[][] matrix) {
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				System.out.print(" " + matrix[i][j]);
			}
			System.out.println();
		}
	}

}
